#include <cstring>
#include <cassert>

#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
BTLeafNode::BTLeafNode()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	btnode->keyCount = 0;
	btnode->ptr = -1;
}

RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	return btnode->keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int keyCount, i;
	char buf[PageFile::PAGE_SIZE];
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	// node is full
	if ((keyCount = btnode->keyCount) == maxKeyCount)
		return RC_NODE_FULL;
	// Iterate over tree
	for (i = 0; i < keyCount; i++){
		// We found the slot to insert the key
		if (key <= btnode->keyPairs[i].key){
			int len = (keyCount - i) * sizeof(struct BTKeyPair);
			if (len > 0){
			// Copy into temporary buffer and then shift over
				memcpy(buf, &btnode->keyPairs[i], len);
				memcpy(&btnode->keyPairs[i + 1], buf, len);
			}
			// Insert the (key, rid) pair
			btnode->keyPairs[i].key = key;
			btnode->keyPairs[i].rid = rid;
			btnode->keyCount++;
			return 0;
		}
	}
	// Maximum key
	btnode->keyPairs[keyCount].key = key;
	btnode->keyPairs[keyCount].rid = rid;
	btnode->keyCount++;
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int keyCount, i;
	RC rc;
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	keyCount = btnode->keyCount;
	siblingKey = btnode->keyPairs[keyCount / 2].key;
	btnode->keyCount = keyCount / 2;
	for (i = keyCount / 2; i < keyCount; i++){
		int split_key;
		RecordId split_rid;

		split_key = btnode->keyPairs[i].key;
		split_rid = btnode->keyPairs[i].rid;
		sibling.insert(split_key, split_rid);
	}
	// Insert the new key into this node
	if (key < siblingKey)
		rc = insert(key, rid);
	else
	// Insert the key into the sibling node
		rc = sibling.insert(key, rid);
	return rc;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int i;
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	for (i = 0; i < btnode->keyCount; i++){
		// Found the key, so return the eid.
		if (btnode->keyPairs[i].key >= searchKey){
			eid = i;
			return 0;
		}
	}
	// No such record exists
	return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	
	// Entry out of bounds
	if (eid < 0 || eid >= btnode->keyCount)
		return RC_NO_SUCH_RECORD;
	key = btnode->keyPairs[eid].key;
	rid = btnode->keyPairs[eid].rid;
	return 0;
}

/*
 * Return the pid of the next sibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	return btnode->ptr;
}

/*
 * Set the pid of the next sibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	btnode->ptr = pid;
	return 0;
}

int BTLeafNode::getHeight()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	return btnode->height;
}

RC BTLeafNode::setHeight(int height)
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	btnode->height = height;
	return 0;
}

BTNonLeafNode::BTNonLeafNode()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	btnode->keyCount = 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	return btnode->keyCount;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int keyCount, i;
	char buf[PageFile::PAGE_SIZE];
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	// node is full
	if ((keyCount = btnode->keyCount) == maxKeyCount)
		return RC_NODE_FULL;
	// Iterate over tree
	for (i = 0; i < keyCount; i++){
		if (key <= btnode->keyPairs[i].key){
			int len = (keyCount - i) * sizeof(struct BTKeyPair);
			if (len > 0){
			// Copy into temporary buffer and then shift
				memcpy(buf, &btnode->keyPairs[i], len);
				memcpy(&btnode->keyPairs[i + 1], buf, len);
			}
			// Insert the (key, rid) pair
			btnode->keyPairs[i].key = key;
			btnode->keyPairs[i].pid = pid;
			btnode->keyCount++;
			return 0;
		}
	}
	// Insert key into the last slot
	btnode->keyPairs[keyCount].key = key;
	btnode->keyPairs[keyCount].pid = pid;
	btnode->keyCount++;
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int keyCount, i;
	RC rc;
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	// Divide the node in half.
	keyCount = btnode->keyCount;
	midKey = btnode->keyPairs[keyCount / 2].key;
	btnode->keyCount  = keyCount / 2;
	// Move half of the keys to the sibling node.
	sibling.setFirstNodePtr(btnode->keyPairs[btnode->keyCount].pid);
	for (i = btnode->keyCount + 1; i < keyCount; i++){
		int split_key;
		PageId split_pid;

		split_key = btnode->keyPairs[i].key;
		split_pid = btnode->keyPairs[i].pid;
		sibling.insert(split_key, split_pid);
	}
	// Insert the new key either into this node or its sibling.
	if (key < midKey)
		rc = insert(key, pid);
	else
		rc = sibling.insert(key, pid);
	return rc;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int keyCount, i;
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	keyCount = btnode->keyCount;
	if (btnode->keyPairs[0].key > searchKey){
		pid = btnode->ptr;
		assert(pid != 0);
		return 0;
	}
	for (i = 1; i < keyCount; i++){
		// We found the key, so return the pid.
		if (btnode->keyPairs[i].key > searchKey){
			pid = btnode->keyPairs[i - 1].pid;
			return 0;
		}
	}
	// Return max key
	pid = btnode->keyPairs[keyCount - 1].pid;
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);

	btnode->keyCount = 1;
	btnode->ptr = pid1;
	btnode->keyPairs[0].key = key;
	btnode->keyPairs[0].pid = pid2;
	return 0;
}

/**
 * Get the height of the tree (only valid on the root).
 */
int BTNonLeafNode::getHeight()
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	return btnode->height;
}

/**
 * Set the height of the tree (only valid on the root).
 */
RC BTNonLeafNode::setHeight(int height)
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	btnode->height = height;
	return 0;
}

RC BTNonLeafNode::setFirstNodePtr(PageId pid)
{
	BTNodeStruct *btnode = reinterpret_cast<BTNodeStruct *>(buffer);
	btnode->ptr = pid;
	return 0;
}
